package com.peng.leetcode.tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * CBTInserter
 * 919. 完全二叉树插入器
 * https://leetcode.cn/problems/complete-binary-tree-inserter/
 *
 * @author: lupeng6
 * @create: 2023/2/12 14:42
 */
public class CBTInserter {

    private TreeNode root;
    private Queue<TreeNode> candidate;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> q = new ArrayDeque<>();
        this.candidate = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n.left != null) {
                q.offer(n.left);
            }
            if (n.right != null) {
                q.offer(n.right);
            }
            if (n.left == null || n.right == null) {
                candidate.offer(n);
            }
        }
    }

    public int insert(int val) {
        TreeNode child = new TreeNode(val);
        TreeNode n = candidate.peek();
        if (n.left == null) {
            n.left = child;
        } else {
            n.right = child;
            candidate.poll();
        }
        candidate.offer(child);
        return n.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
